#include <iostream>
#include <stdlib.h>
#include <vector>
using namespace std;


void sayHello() {
    cout << "hello world" << endl;
}

void testFunc1() {
    // - 俩个整形数据使用异或进行交换
    /**
     * int temp = a ^ b
     * a = temp ^ b
     * b = temp ^ a
    */
    int a = 121, b = 235;
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;
    cout << "a: " << a << endl;
    cout << "b: " << b << endl;
}

void testFunc2() {
    // // - 对一个整形数据 取反 + 1 再与源整形数据 & 操作可以找到源整形数据 二进制最右侧的1
    // int c = 5;
    // char str1[64] = {0}, str2[64] = {0};
    // // warning C4996: 'itoa': The POSIX name for this item is deprecated. Instead, use the ISO C and C++ conformant name: _itoa. See online help for details.
    // // 使用 _itoa_s 替换 itoa
    // _itoa_s(c, str1, 2);
    // cout << "c: " << c << "  " << str1 << endl;
    // _itoa_s(~c, str2, 2);
    // cout << "~c: " << ~c << "  " << str2 << endl;

    /**
     * 问：一个数组中(正整数)，两种数出现奇数次，其余数全部出现偶数次，求出现奇数次的两种数?
     */
    int arr[] = {10, 10, 10, 2, 2, 3, 3, 5, 5, 5};
    int eor1 = 0, eor2 = 0;
    int len = sizeof(arr) / sizeof(arr[0]);
    for(int i = 0; i < len; i++) {
        eor1 ^= arr[i];
    }
    int rightOne = eor1 & (~eor1 + 1);
    for(int i = 0; i < len; i++) {
        if((arr[i] & rightOne) == 0) {
            eor2 ^= arr[i];
        }
    }

    int b = eor1 ^ eor2;
    cout << "a: " << eor2 << " b: " << b << endl;
}


void printVector(vector<int>& num) {
    // for(vector<int>::iterator it = num.begin(); it != num.end(); it++) {
    //     cout << *it << " ";
    // }
    // cout << endl;
    for(int i = 0; i < num.size(); i++) {
        cout << num[i] << " ";
    }
    cout << endl;
}
void merge(vector<int>& num1, int m, vector<int>& num2, int n) {
    vector<int> numHelp;
    vector<int>::iterator it1 = num1.begin(), it2 = num2.begin();
    while(it1 != num1.end() && it2 != num2.end()) {
        if(*it1 > *it2) {
            numHelp.push_back(*it2);
            it2++;
        } else {
            numHelp.push_back(*it1);
            it1++;
        }
    }
    while(it1 == num1.end() && it2 != num2.end()) {
        numHelp.push_back(*it2);
        it2++;
    }
    while (it1 != num1.end() && it2 == num2.end()) {
        numHelp.push_back(*it1);
        it1++;
    }
    num1 = numHelp;

    printVector(num1);
}
void testFunc3() {
    vector<int> num1;
    num1.push_back(1);
    num1.push_back(2);
    num1.push_back(3);
    cout << "print num1: ";
    printVector(num1);

    vector<int> num2;
    num2.push_back(2);
    num2.push_back(5);
    num2.push_back(6);
    cout << "print num2: ";
    printVector(num2);

    merge(num1, 6, num2, 3);
}

void merge2(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    // 88.合并两个有序数组
    // 1.归并解法
    // vector<int> numHelp;
    // int numIdx1 = 0, numIdx2 = 0;
    // while(numIdx1 < m && numIdx2 < n) {
    //     if(nums1[numIdx1] > nums2[numIdx2]) {
    //         numHelp.push_back(nums2[numIdx2++]);
    //     } else {
    //         numHelp.push_back(nums1[numIdx1++]);
    //     }
    // }
    // while(numIdx1 == m && numIdx2 < n) {
    //     numHelp.push_back(nums2[numIdx2++]);
    // }
    // while(numIdx1 < m && numIdx2 == n) {
    //     numHelp.push_back(nums1[numIdx1++]);
    // }
    // nums1 = numHelp;
    // 2.1从后往前 大的先放入nums1
    int idx = m + n - 1;
    m--, n--;
    while(m >= 0 && n >= 0) {
        if(nums1[m] > nums2[n]) {
            nums1[idx--] = nums1[m--];
        } else {
            nums1[idx--] = nums2[n--];
        }
    }
    while(n >= 0) {
        nums1[idx--] = nums2[n--];
    }
    while(m >= 0) {
        nums1[idx--] = nums1[m--];
    }
    // 2.2简化2.1的写法
    //    结束条件为第二个数组全部插入
    // while(n >= 0) {
    //     while(m >= 0 && nums1[m] > nums2[n]) {
    //         nums1[idx--] = nums1[m--];
    //     }
    //     nums1[idx--] = nums2[n--];
    // }

    cout << "the result: " << endl;
    printVector(nums1);
}
void testFunc4() {
    vector<int> num1, num2;
    num1.push_back(1);
    num1.push_back(2);
    num1.push_back(3);
    num1.push_back(0);
    num1.push_back(0);
    num1.push_back(0);

    num2.push_back(2);
    num2.push_back(5);
    num2.push_back(6);

    merge2(num1, 3, num2, num2.size());
}

void mergeFunc(vector<int>& vec, int L, int R, int mid) {
    vector<int> vecHelp;
    int idx1 = L, idx2 = mid + 1;
    while(idx1 <= mid && idx2 <= R) {
        if(vec[idx1] > vec[idx2]) {
            vecHelp.push_back(vec[idx2++]);
        } else {
            vecHelp.push_back(vec[idx1++]);
        }
    }
    while(idx1 <= mid) {
        vecHelp.push_back(vec[idx1++]);
    }
    while(idx2 <= R) {
        vecHelp.push_back(vec[idx2++]);
    }
    cout << "vecHelp: " << endl;
    printVector(vecHelp);
    for(int i = 0; i < vecHelp.size(); i++) {
        vec[L + i] = vecHelp[i];
    }
}
void process(vector<int>& vec, int L, int R) {
    if(L == R) return;
    int mid = L + ((R - L) >> 1);
    cout << "mid: " << mid << endl;
    process(vec, L, mid);
    process(vec, mid + 1, R);
    mergeFunc(vec, L, R, mid);
}
void mergeSort(vector<int>& vec) {
    if(vec.size() < 2) {
        return;
    }

    process(vec, 0, vec.size() - 1);
}
void testFunc5() {
    vector<int> nums;
    nums.push_back(10);
    nums.push_back(6);
    nums.push_back(3);
    nums.push_back(9);
    nums.push_back(8);
    nums.push_back(5);
    nums.push_back(1546945);
    mergeSort(nums);

    cout << "after sort: "  << endl;
    printVector(nums);
}

double champagneTower(int poured, int query_row, int query_glass) {
    // 799.香槟塔
    vector<double> row = {(double)poured};
    for(int i = 1; i <= query_row; i++) {
        vector<double> nextRow(i + 1, 0.0);
        for(int j = 0; j < row.size(); j++) {
            if(row[j] > 1) {
                nextRow[j] += (row[j] - 1) / 2;
                nextRow[j + 1] += (row[j] - 1) / 2;
            }
        }
        row = nextRow;
    }
    return min(1.0, row[query_glass]);
}
void testFunc6() {
    double res = champagneTower(100000009, 33, 17);
    cout << "res: " << res << endl;
}


